| 翻訳と辞書 |
| Unpredictable permutation ： ウィキペディア英語版 |
Unpredictable permutation
In mathematical cryptography, an unpredictable permutation (UP) ''F''''k'' is a permutation whose values cannot be predicted by a fast randomized algorithm. Unpredictable permutations may be used as a cryptographic primitive, a building block for cryptographic systems with more complex properties.
==Definition==
An adversary for an unpredictable permutation is defined to be an algorithm that is given access to an oracle for both forward and inverse permutation operations. The oracle is given a challenge input ''k'' and is asked to predict the value of ''F''''k''. It is allowed to make a series of queries to the oracle to help it make this prediction, but is not allowed to query the value of ''k'' itself.〔.〕
A randomized algorithm for generating permutations generates an unpredictable permutation if its outputs are permutations on a set of items (described by length-''n'' binary strings) that cannot be predicted with accuracy significantly better than random by an adversary that makes a polynomial (in ''n'') number of queries to the oracle prior to the challenge round, whose running time is polynomial in ''n'', and whose error probability is less than 1/2 for all instances. That is, it cannot be predicted in the complexity class PP, relativized by the oracle for the permutation.〔
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Unpredictable permutation」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|